package common.sort;

/**
 * 原理:
 * 升级版的选择排序
 * <p>
 * 堆的存储:
 * 一般用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2；其左右子结点分别为 (2i + 1)、(2i + 2)
 * <p>
 * https://zhuanlan.zhihu.com/p/124885051
 * <p>
 * 1.创建最大堆，此时最大值是根节点
 * 2.根节点与最后一个元素交换
 * 3.再次创建根节点与最后一个元素前一个节点为最大堆，如此反复，既可以得到一个递增序列
 * <p>
 * 使用场景:
 * 最大值，最小值
 */
public class HeapSort implements Sort {

    @Override
    public void sort(int[] array) {
        int LEN = array.length;
        if (LEN < 2) {
            return;
        }

        // 最后一个节点位置
        int lastPos = LEN - 1;
        // 最后一个节点父节点 (lastPos - 1) / 2
        int lastLeafParentPos = (lastPos - 1) >> 1;
        for (int i = lastLeafParentPos; i >= 0; i--) {
            maxHeap(array, i, lastPos);
        }

        // 对堆化的数据进行排序
        for (int i = lastPos; i > 0; i--) {
            swap(array, 0, i);
            maxHeap(array, 0, i - 1);
        }
    }

    void maxHeap(int[] array, int beginParentPos, int lastPos) {
        // 左叶子节点 2*beginParentPos + 1
        int leftChildPos = (beginParentPos << 1) + 1;
        // 右叶子节点 2*beginParentPos + 2
        int rightChildPos = leftChildPos + 1;

        // 左子节点索引超出计算范围，直接返回
        if (leftChildPos > lastPos) {
            return;
        }

        // 默认左孩子节点为最大值
        int maxPos = leftChildPos;
        // 先判断左右节点哪个节点比较大
        if (rightChildPos <= lastPos && array[rightChildPos] > array[leftChildPos]) {
            maxPos = rightChildPos;
        }

        if (array[maxPos] > array[beginParentPos]) {
            swap(array, beginParentPos, maxPos);
            // 节点被置换后，需要重新判断子节点的有效性
            maxHeap(array, maxPos, lastPos);
        }
    }

    void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}
